1508. Окна роз
Мистер Арнольд Геральд Ностик
занимается разработкой главного окна нового городского собора. Окно
круглое, его диаметр равен 2r. Поскольку мистер A. Г. Ностик
немножко знает о девственницах, святых и ангелах, он призадумался над
геометрическим шаблоном: пусть n
четное целое число, как минимум 4. Мистер Ностик планирует выбрать n точек, каждую на расстоянии r от центра окна, так чтобы они
образовали правильный многоугольник (на картинке приведен пример с n = 8). Потом эти точки соединяются отрезками
и полученные области закрашиваются как показано ниже (цвета выбираются
произвольно). Заметим, что при n = 8
будет всего четыре области. Пронумеруем эти области 1, 2, 3 и 4 начиная с
центральной. В общем случае образуется n
/ 2 областей.
Помогите мистеру Ностику узнать,
сколько стекла каждого цвета необходимо приобрести для выкладки окна.
Вход. Первая строка содержит
количество тестов t. Далее следуют t строк, каждая из которых содержит действительное число r (1 ≤ r ≤ 100), четное целое n
(4 ≤ n ≤ 40), и k (1 ≤ k ≤ n / 2).
Выход. Для каждой входной тройки r, n,
k в отдельной строке вывести площадь k-ой области окна, округленную до
четырех десятичных знаков.
Пример входа
4
50 8 3
9.238794 8 2
10 4 1
20 4 1
Пример выхода
2928.9322
100.0000
200.0000
800.0000
Правильный восьмиугольник Окно роз с 8 точками
в
окружности
Первая область окна роз Вторая область окна роз
Третья область окна роз Четвертая область окна роз
РЕШЕНИЕ
геометрия
Анализ алгоритма
k-ую область окна роз вместе со всеми внутренними областями
будем называть k-ым многоугольником. Она в свою очередь будет представляет
собой правильный n-угольник.
Радиусом окружности, описанной
вокруг такого k-ого многоугольника,
будет отрезок OP. Точка P образована пересечением отрезков AB и CD. При этом точки A и C, а также B и D идут
последовательно по окружности, а между A и B лежит некоторое число точек. Упомянутые точки имеют координаты:
A(r, 0), 
, 
, 
.
Строим уравнения прямых,
проходящих через AB и CD. По правилу Крамера ищем точку их пересечения, то есть координаты точки P.
Площадь k-ого многоугольника равна n площадям равнобедренных треугольников с боковой стороной
OP и углом при вершине 2π
/ n. Их площади равны 
.
Искомую площадь k-ой области находим как разницу площадей k-ого многоугольника и (k – 1)-го многоугольника.
Реализация алгоритма
Уравнением прямой, проходящей через точки (x1, y1) и (x2, y2), будет ax + by
+ c = 0.
void GetLine(double
x1,double y1, double
x2, double y2,
double
*a, double *b, double
*c)
{
*a = y2 - y1;
*b = -(x2 - x1);
*c = -x1*(y2 - y1) + y1*(x2 - x1);
}
Точкой пересечения прямых a1x + b1y = c1 и a2x + b2y = c2 будет P(x, y).
void GetPoint(double
a1,double b1, double
c1,
double
a2, double b2, double
c2, double *x, double
*y)
{
double d =
a1*b2 - a2*b1;
*x = (c1*b2 - c2*b1) / d;
*y = (a1*c2 - a2*c1) / d;
}
Вычисление площади k-ого многоугольника. Точка P имеет
кординаты (x, y), а d = OP2.
double Area(double
x, double y)
{
double d =
x*x+y*y;
return
n*d*sin(2*PI/n)/2;
}
double FindSquare(int
k)
{
double
a1,b1,c1,a2,b2,c2;
double x,y;
GetLine(r,0,r*cos(2*PI*k/n),r*sin(2*PI*k/n),&a1,&b1,&c1);
GetLine(r*cos(2*PI/n),r*sin(2*PI/n),r*cos(2*PI*(k+1)/n),
r*sin(2*PI*(k+1)/n),&a2,&b2,&c2);
GetPoint(a1,b1,-c1,a2,b2,-c2,&x,&y);
return
Area(x,y);
}
Основная часть программы.
PI =
2*acos(0.0);
scanf("%d",&m);
for(i = 0; i < m; i++)
{
scanf("%lf %d
%d",&r,&n,&k);
if (k == n/2)
UpperS = PI*r*r;
else UpperS =
FindSquare(n/2-k);
DownS = FindSquare(n/2-k+1);
Res = UpperS - DownS;
printf("%.4lf\n",Res);
}